home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / russell / gc32.lha / alloc.c next >
C/C++ Source or Header  |  1993-07-21  |  17KB  |  581 lines
  1. /*
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1993 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to copy this garbage collector for any purpose,
  9.  * provided the above notices are retained on all copies.
  10.  *
  11.  */
  12.  
  13.  
  14. # include <stdio.h>
  15. # include <signal.h>
  16. # include <sys/types.h>
  17. # include "gc_private.h"
  18.  
  19. /*
  20.  * Separate free lists are maintained for different sized objects
  21.  * up to MAXOBJSZ.
  22.  * The call GC_allocobj(i,k) ensures that the freelist for
  23.  * kind k objects of size i points to a non-empty
  24.  * free list. It returns a pointer to the first entry on the free list.
  25.  * In a single-threaded world, GC_allocobj may be called to allocate
  26.  * an object of (small) size i as follows:
  27.  *
  28.  *            opp = &(GC_objfreelist[i]);
  29.  *            if (*opp == 0) GC_allocobj(i, NORMAL);
  30.  *            ptr = *opp;
  31.  *            *opp = obj_link(ptr);
  32.  *
  33.  * Note that this is very fast if the free list is non-empty; it should
  34.  * only involve the execution of 4 or 5 simple instructions.
  35.  * All composite objects on freelists are cleared, except for
  36.  * their first word.
  37.  */
  38.  
  39. /*
  40.  *  The allocator uses GC_allochblk to allocate large chunks of objects.
  41.  * These chunks all start on addresses which are multiples of
  42.  * HBLKSZ.   Each allocated chunk has an associated header,
  43.  * which can be located quickly based on the address of the chunk.
  44.  * (See headers.c for details.) 
  45.  * This makes it possible to check quickly whether an
  46.  * arbitrary address corresponds to an object administered by the
  47.  * allocator.
  48.  */
  49.  
  50. word GC_non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
  51.  
  52. word GC_gc_no = 0;
  53.  
  54. int GC_incremental = 0;    /* By default, stop the world.    */
  55.  
  56. int GC_full_freq = 3;       /* Every 4th collection is a full    */
  57.                /* collection.            */
  58.  
  59. char * GC_copyright[] =
  60. {"Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers",
  61. "Copyright (c) 1991-1993 by Xerox Corporation.  All rights reserved.",
  62. "THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY",
  63. " EXPRESSED OR IMPLIED.  ANY USE IS AT YOUR OWN RISK."};
  64.  
  65.  
  66. /* some more variables */
  67.  
  68. extern signed_word GC_mem_found;  /* Number of reclaimed longwords    */
  69.                   /* after garbage collection          */
  70.  
  71. bool GC_dont_expand = 0;
  72.  
  73. word GC_free_space_divisor = 4;
  74.  
  75. /* Return the minimum number of words that must be allocated between    */
  76. /* collections to amortize the collection cost.                */
  77. static word min_words_allocd()
  78. {
  79.     int dummy;
  80. #   ifdef THREADS
  81.      /* We punt, for now. */
  82.      register signed_word stack_size = 10000;
  83. #   else
  84.         register signed_word stack_size = (ptr_t)(&dummy) - GC_stackbottom;
  85. #   endif
  86.     register word total_root_size;  /* includes double stack size,    */
  87.                         /* since the stack is expensive    */
  88.                         /* to scan.                */
  89.     
  90.     if (stack_size < 0) stack_size = -stack_size;
  91.     total_root_size = 2 * stack_size + GC_root_size;
  92.     if (GC_incremental) {
  93.         return(BYTES_TO_WORDS(GC_heapsize + total_root_size)
  94.                / (2 * GC_free_space_divisor));
  95.     } else {
  96.         return(BYTES_TO_WORDS(GC_heapsize + total_root_size)
  97.                / GC_free_space_divisor);
  98.     }
  99. }
  100.  
  101. /* Return the number of words allocated, adjusted for explicit storage    */
  102. /* management, etc..  This number is used in deciding when to trigger    */
  103. /* collections.                                */
  104. word GC_adj_words_allocd()
  105. {
  106.     register signed_word result;
  107.     register signed_word expl_managed =
  108.             BYTES_TO_WORDS((long)GC_non_gc_bytes
  109.                     - (long)GC_non_gc_bytes_at_gc);
  110.     
  111.     /* Don't count what was explicitly freed, or newly allocated for    */
  112.     /* explicit management.  Note that deallocating an explicitly    */
  113.     /* managed object should not alter result, assuming the client    */
  114.     /* is playing by the rules.                        */
  115.     result = (signed_word)GC_words_allocd
  116.              - (signed_word)GC_mem_freed - expl_managed;
  117.     if (result > (signed_word)GC_words_allocd) result = GC_words_allocd;
  118.         /* probably client bug or unfortunate scheduling */
  119.     result += GC_words_wasted;
  120.          /* This doesn't reflect useful work.  But if there is lots of    */
  121.          /* new fragmentation, the same is probably true of the heap,    */
  122.          /* and the collection will be correspondingly cheaper.        */
  123.     if (result < (signed_word)(GC_words_allocd >> 2)) {
  124.         /* Always count at least 1/8 of the allocations.  We don't want    */
  125.         /* to collect too infrequently, since that would inhibit    */
  126.         /* coalescing of free storage blocks.                */
  127.         /* This also makes us partially robust against client bugs.    */
  128.         return(GC_words_allocd >> 3);
  129.     } else {
  130.         return(result);
  131.     }
  132. }
  133.  
  134.  
  135. /* Clear up a few frames worth og garbage left at the top of the stack.    */
  136. /* This is used to prevent us from accidentally treating garbade left    */
  137. /* on the stack by other parts of the collector as roots.  This     */
  138. /* differs from the code in misc.c, which actually tries to keep the    */
  139. /* stack clear of long-lived, client-generated garbage.            */
  140. void GC_clear_a_few_frames()
  141. {
  142. #   define NWORDS 64
  143.     word frames[NWORDS];
  144.     register int i;
  145.     
  146.     for (i = 0; i < NWORDS; i++) frames[i] = 0;
  147. }
  148.  
  149. /* Have we allocated enough to amortize a collection? */
  150. bool GC_should_collect()
  151. {
  152.     return(GC_adj_words_allocd() >= min_words_allocd());
  153. }
  154.  
  155. /* 
  156.  * Initiate a garbage collection if appropriate.
  157.  * Choose judiciously
  158.  * between partial, full, and stop-world collections.
  159.  * Assumes lock held, signals disabled.
  160.  */
  161. void GC_maybe_gc()
  162. {
  163.     static int n_partial_gcs = 0;
  164.     if (GC_should_collect()) {
  165.         if (!GC_incremental) {
  166.             GC_gcollect_inner();
  167.             n_partial_gcs = 0;
  168.         } else if (n_partial_gcs >= GC_full_freq) {
  169.             GC_initiate_full();
  170.             n_partial_gcs = 0;
  171.         } else {
  172.             GC_initiate_partial(GC_gc_no+1);
  173.             n_partial_gcs++;
  174.         }
  175.     }
  176. }
  177.  
  178. /*
  179.  * Stop the world garbage collection.  Assumes lock held, signals disabled.
  180.  */
  181. bool GC_gcollect_inner()
  182. {
  183. #   ifdef PRINTSTATS
  184.     GC_printf2(
  185.        "Initiating full world-stop collection %lu after %ld allocd bytes\n",
  186.        (unsigned long) GC_gc_no+1,
  187.        (long)WORDS_TO_BYTES(GC_words_allocd));
  188. #   endif
  189.     GC_promote_black_lists();
  190.     /* GC_reclaim_or_delete_all();  -- not needed: no intervening allocation */
  191.     GC_clear_marks();
  192.     STOP_WORLD();
  193.     GC_stopped_mark();
  194.     START_WORLD();
  195.     GC_finish_collection();
  196. }
  197.  
  198. /*
  199.  * Perform n units of garbage collection work.  A unit is intended to touch
  200.  * roughly a GC_RATE pages.  Every once in a while, we do more than that.
  201.  */
  202. # define GC_RATE 8
  203. void GC_collect_a_little(n)
  204. int n;
  205. {
  206.     register int i;
  207.     
  208.     if (GC_collection_in_progress()) {
  209.         for (i = 0; i < GC_RATE*n; i++) {
  210.             if (GC_mark_some()) {
  211.                 /* Need to finish a collection */
  212.                 STOP_WORLD();
  213.                 GC_stopped_mark();
  214.                 START_WORLD();
  215.                 GC_finish_collection();
  216.                 break;
  217.             }
  218.         }
  219.     } else {
  220.         GC_maybe_gc();
  221.     }
  222. }
  223.  
  224. /*
  225.  * World-stopped mark phase.  Assumes lock is held, signals are disabled,
  226.  * and the world is stopped.
  227.  */
  228. void GC_stopped_mark()
  229. {
  230. #   ifdef PRINTTIMES
  231.     CLOCK_TYPE start_time;
  232.     CLOCK_TYPE done_time;
  233.     
  234.     GET_TIME(start_time);
  235. #   endif
  236. #   ifdef PRINTSTATS
  237.     GC_printf2("Collection %lu reclaimed %ld bytes\n",
  238.           (unsigned long) GC_gc_no,
  239.              (long)WORDS_TO_BYTES(GC_mem_found));
  240. #   endif
  241.     GC_gc_no++;
  242. #   ifdef PRINTSTATS
  243.       GC_printf3(
  244.            "--> Collection number %lu after %lu allocated + %lu wasted bytes\n",
  245.           (unsigned long) GC_gc_no,
  246.           (unsigned long) WORDS_TO_BYTES(GC_words_allocd),
  247.           (unsigned long) WORDS_TO_BYTES(GC_words_wasted));
  248.       GC_printf1("---> heapsize = %lu bytes\n",
  249.                   (unsigned long) GC_heapsize);
  250.       /* Printf arguments may be pushed in funny places.  Clear the    */
  251.       /* space.                                */
  252.       GC_printf0("");
  253. #   endif                  
  254.  
  255.     /* Mark from all roots.  */
  256.         /* Minimize junk left in my registers and on the stack */
  257.             GC_clear_a_few_frames();
  258.             GC_noop(0,0,0,0,0,0);
  259.     GC_initiate_partial(GC_gc_no);
  260.     while(!GC_mark_some());
  261.  
  262.     /* Check all debugged objects for consistency */
  263.         if (GC_debugging_started) {
  264.             (*GC_check_heap)();
  265.         }
  266.     
  267. #   ifdef PRINTTIMES
  268.     GET_TIME(done_time);
  269.     GC_printf1("World-stopped marking took %lu msecs\n",
  270.                MS_TIME_DIFF(done_time,start_time));
  271. #   endif
  272.  
  273. }
  274.  
  275.  
  276. /* Finish up a collection.  Assumes lock is held, signals are disabled,    */
  277. /* but the world is otherwise running.                    */
  278. void GC_finish_collection()
  279. {
  280. #   ifdef PRINTTIMES
  281.     CLOCK_TYPE start_time;
  282.     CLOCK_TYPE finalize_time;
  283.     CLOCK_TYPE done_time;
  284.     
  285.     GET_TIME(start_time);
  286.     finalize_time = start_time;
  287. #   endif
  288.  
  289. #   ifdef GATHERSTATS
  290.         GC_mem_found = 0;
  291. #   endif
  292. #   ifdef FIND_LEAK
  293.       /* Mark all objects on the free list.  All objects should be */
  294.       /* marked when we're done.                   */
  295.     {
  296.       register word size;        /* current object size        */
  297.       register ptr_t p;    /* pointer to current object    */
  298.       register struct hblk * h;    /* pointer to block containing *p */
  299.       register hdr * hhdr;
  300.       register int word_no;           /* "index" of *p in *q          */
  301.       int kind;
  302.  
  303.       for (kind = 0; kind < GC_n_kinds; kind++) {
  304.         for (size = 1; size <= MAXOBJSZ; size++) {
  305.           for (p= GC_obj_kinds[kind].ok_freelist[size];
  306.                p != 0; p=obj_link(p)){
  307.         h = HBLKPTR(p);
  308.         hhdr = HDR(h);
  309.         word_no = (((word *)p) - ((word *)h));
  310.         set_mark_bit_from_hdr(hhdr, word_no);
  311.           }
  312.         }
  313.       }
  314.     }
  315.       /* Check that everything is marked */
  316.     GC_start_reclaim(TRUE);
  317. #   else
  318.  
  319.       GC_finalize();
  320. #     ifdef STUBBORN_ALLOC
  321.         GC_clean_changing_list();
  322. #     endif
  323.  
  324. #     ifdef PRINTTIMES
  325.     GET_TIME(finalize_time);
  326. #     endif
  327.  
  328.       /* Clear free list mark bits, in case they got accidentally marked   */
  329.       /* Note: HBLKPTR(p) == pointer to head of block containing *p        */
  330.       /* Also subtract memory remaining from GC_mem_found count.           */
  331.       /* Note that composite objects on free list are cleared.             */
  332.       /* Thus accidentally marking a free list is not a problem;  only     */
  333.       /* objects on the list itself will be marked, and that's fixed here. */
  334.       {
  335.     register word size;        /* current object size        */
  336.     register ptr_t p;    /* pointer to current object    */
  337.     register struct hblk * h;    /* pointer to block containing *p */
  338.     register hdr * hhdr;
  339.     register int word_no;           /* "index" of *p in *q          */
  340.     int kind;
  341.  
  342.     for (kind = 0; kind < GC_n_kinds; kind++) {
  343.       for (size = 1; size <= MAXOBJSZ; size++) {
  344.         for (p= GC_obj_kinds[kind].ok_freelist[size];
  345.              p != 0; p=obj_link(p)){
  346.         h = HBLKPTR(p);
  347.         hhdr = HDR(h);
  348.         word_no = (((word *)p) - ((word *)h));
  349.         clear_mark_bit_from_hdr(hhdr, word_no);
  350.         GC_mem_found -= size;
  351.         }
  352.       }
  353.     }
  354.       }
  355.  
  356.  
  357. #     ifdef PRINTSTATS
  358.     GC_printf1("Bytes recovered before sweep - f.l. count = %ld\n",
  359.               (long)WORDS_TO_BYTES(GC_mem_found));
  360. #     endif
  361.  
  362.     /* Reconstruct free lists to contain everything not marked */
  363.       GC_start_reclaim(FALSE);
  364.     
  365. #   endif /* !FIND_LEAK */
  366.  
  367. #   ifdef PRINTSTATS
  368.     GC_printf2(
  369.           "Immediately reclaimed %ld bytes in heap of size %lu bytes\n",
  370.               (long)WORDS_TO_BYTES(GC_mem_found),
  371.               (unsigned long)GC_heapsize);
  372.     GC_printf2("%lu (atomic) + %lu (composite) bytes in use\n",
  373.                (unsigned long)WORDS_TO_BYTES(GC_atomic_in_use),
  374.                (unsigned long)WORDS_TO_BYTES(GC_composite_in_use));
  375. #   endif
  376.  
  377.     /* Reset or increment counters for next cycle */
  378.       GC_words_allocd_before_gc += GC_words_allocd;
  379.       GC_non_gc_bytes_at_gc = GC_non_gc_bytes;
  380.       GC_words_allocd = 0;
  381.       GC_words_wasted = 0;
  382.       GC_mem_freed = 0;
  383.       
  384. #   ifdef PRINTTIMES
  385.     GET_TIME(done_time);
  386.     GC_printf2("Finalize + initiate sweep took %lu + %lu msecs\n",
  387.                MS_TIME_DIFF(finalize_time,start_time),
  388.                MS_TIME_DIFF(done_time,finalize_time));
  389. #   endif
  390. }
  391.  
  392. /* Externally callable routine to invoke full, stop-world collection */
  393. void GC_gcollect()
  394. {
  395.     DCL_LOCK_STATE;
  396.     
  397.     DISABLE_SIGNALS();
  398.     LOCK();
  399.     if (!GC_is_initialized) GC_init_inner();
  400.     /* Minimize junk left in my registers */
  401.       GC_noop(0,0,0,0,0,0);
  402.     (void) GC_gcollect_inner();
  403.     UNLOCK();
  404.     ENABLE_SIGNALS();
  405. }
  406.  
  407. word GC_n_heap_sects = 0;    /* Number of sections currently in heap. */
  408.  
  409. /*
  410.  * Use the chunk of memory starting at p of syze bytes as part of the heap.
  411.  * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE.
  412.  */
  413. void GC_add_to_heap(p, bytes)
  414. struct hblk *p;
  415. word bytes;
  416. {
  417.     word words;
  418.     
  419.     if (GC_n_heap_sects >= MAX_HEAP_SECTS) {
  420.         GC_err_printf0(
  421.             "Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
  422.         ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS");
  423.     }
  424.     if (!GC_install_header(p)) {
  425.         /* This is extremely unlikely. Can't add it.  This will        */
  426.         /* almost certainly result in a    0 return from the allocator,    */
  427.         /* which is entirely appropriate.                */
  428.         return;
  429.     }
  430.     GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p;
  431.     GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes;
  432.     GC_n_heap_sects++;
  433.     words = BYTES_TO_WORDS(bytes - HDR_BYTES);
  434.     HDR(p) -> hb_sz = words;
  435.     GC_freehblk(p);
  436.     GC_heapsize += bytes;
  437.     if ((ptr_t)p <= GC_least_plausible_heap_addr
  438.         || GC_least_plausible_heap_addr == 0) {
  439.         GC_least_plausible_heap_addr = (ptr_t)p - sizeof(word);
  440.             /* Making it a little smaller than necessary prevents    */
  441.             /* us from getting a false hit from the variable    */
  442.             /* itself.  There's some unintentional reflection    */
  443.             /* here.                        */
  444.     }
  445.     if ((ptr_t)p + bytes >= GC_greatest_plausible_heap_addr) {
  446.         GC_greatest_plausible_heap_addr = (ptr_t)p + bytes;
  447.     }
  448. }
  449.  
  450. ptr_t GC_least_plausible_heap_addr = (ptr_t)ONES;
  451. ptr_t GC_greatest_plausible_heap_addr = 0;
  452.  
  453. ptr_t GC_max(x,y)
  454. ptr_t x, y;
  455. {
  456.     return(x > y? x : y);
  457. }
  458.  
  459. ptr_t GC_min(x,y)
  460. ptr_t x, y;
  461. {
  462.     return(x < y? x : y);
  463. }
  464.  
  465. /*
  466.  * this explicitly increases the size of the heap.  It is used
  467.  * internally, but my also be invoked from GC_expand_hp by the user.
  468.  * The argument is in units of HBLKSIZE.
  469.  * Returns FALSE on failure.
  470.  */
  471. bool GC_expand_hp_inner(n)
  472. word n;
  473. {
  474.     word bytes = n * HBLKSIZE;
  475.     struct hblk * space = GET_MEM(bytes);
  476.     word expansion_slop;    /* Number of bytes by which we expect the */
  477.                     /* heap to expand soon.              */
  478.  
  479.     if (n > 2*GC_hincr) {
  480.     GC_hincr = n/2;
  481.     }
  482.     if( space == 0 ) {
  483.     return(FALSE);
  484.     }
  485. #   ifdef PRINTSTATS
  486.     GC_printf2("Increasing heap size by %lu after %lu allocated bytes\n",
  487.                (unsigned long)bytes,
  488.                (unsigned long)WORDS_TO_BYTES(GC_words_allocd));
  489. #   endif
  490.     expansion_slop = 8 * WORDS_TO_BYTES(min_words_allocd());
  491.     if (5 * HBLKSIZE * MAXHINCR > expansion_slop) {
  492.         expansion_slop = 5 * HBLKSIZE * MAXHINCR;
  493.     }
  494.     if (GC_last_heap_addr == 0 && !((word)space & SIGNB)
  495.         || GC_last_heap_addr != 0 && GC_last_heap_addr < (ptr_t)space) {
  496.         /* Assume the heap is growing up */
  497.         GC_greatest_plausible_heap_addr =
  498.             GC_max(GC_greatest_plausible_heap_addr,
  499.                    (ptr_t)space + bytes + expansion_slop);
  500.     } else {
  501.         /* Heap is growing down */
  502.         GC_least_plausible_heap_addr =
  503.             GC_min(GC_least_plausible_heap_addr,
  504.                    (ptr_t)space - expansion_slop);
  505.     }
  506.     GC_prev_heap_addr = GC_last_heap_addr;
  507.     GC_last_heap_addr = (ptr_t)space;
  508.     GC_add_to_heap(space, bytes);
  509.     return(TRUE);
  510. }
  511.  
  512. /* Really returns a bool, but it's externally visible, so that's clumsy. */
  513. int GC_expand_hp(n)
  514. int n;
  515. {
  516.     int result;
  517.     DCL_LOCK_STATE;
  518.     
  519.     DISABLE_SIGNALS();
  520.     LOCK();
  521.     if (!GC_is_initialized) GC_init_inner();
  522.     result = (int)GC_expand_hp_inner((word)n);
  523.     UNLOCK();
  524.     ENABLE_SIGNALS();
  525.     return(result);
  526. }
  527.  
  528. bool GC_collect_or_expand(needed_blocks)
  529. word needed_blocks;
  530. {
  531.     static int count = 0;  /* How many failures? */
  532.     
  533.     if (!GC_incremental && !GC_dont_gc && GC_should_collect()) {
  534.       GC_gcollect_inner();
  535.     } else {
  536.       if (!GC_expand_hp_inner(GC_hincr + needed_blocks)
  537.         && !GC_expand_hp_inner(needed_blocks)) {
  538.           if (count++ < 20) {
  539.               WARN("Out of Memory!  Trying to continue ...\n");
  540.         GC_gcollect_inner();
  541.     } else {
  542.         WARN("Out of Memory!  Returning NIL!\n");
  543.         return(FALSE);
  544.     }
  545.       }
  546.       update_GC_hincr;
  547.     }
  548.     return(TRUE);
  549. }
  550.  
  551. /*
  552.  * Make sure the object free list for sz is not empty.
  553.  * Return a pointer to the first object on the free list.
  554.  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
  555.  * Assumes we hold the allocator lock and signals are disabled.
  556.  *
  557.  */
  558. ptr_t GC_allocobj(sz, kind)
  559. word sz;
  560. int kind;
  561. {
  562.     register ptr_t * flh = &(GC_obj_kinds[kind].ok_freelist[sz]);
  563.     
  564.     if (sz == 0) return(0);
  565.  
  566.     while (*flh == 0) {
  567.       /* Do our share of marking work */
  568.         if(GC_incremental && !GC_dont_gc) GC_collect_a_little(1);
  569.       /* Sweep blocks for objects of this size */
  570.           GC_continue_reclaim(sz, kind);
  571.       if (*flh == 0) {
  572.         GC_new_hblk(sz, kind);
  573.       }
  574.       if (*flh == 0) {
  575.         if (!GC_collect_or_expand((word)1)) return(0);
  576.       }
  577.     }
  578.     
  579.     return(*flh);
  580. }
  581.